Abstract

In this work we provide ac onvergence analysis for the quasi-optimal
version of the Stochastic Sparse Grid Collocation method we had presented in
our previous work “On the optimal polynomial approximation of Stochastic
PDEs by Galerkin and Collocation methods” [6]. Here the construction of a
sparse grid is recast into a knapsack problem: a profit is assigned to each hi-
erarchical surplus and only the most profitable ones are added to the sparse
grid. The convergence rate of the sparse grid approximation error with respect
to the number of points in the grid is then shown to depend on weighted
summability properties of the sequence of profits. This argument is very gen-
eral and can be applied to sparse grids built with any uni-variate family of
points, both nested and non-nested. As an example, we apply such quasi-
optimal sparse grid to the solution of a particular elliptic PDE with stochastic
diffusion coefficients, namely the “inclusions problem”: we detail the conver-
gence estimate obtained in this case, using polynomial interpolation on either
nested (Clenshaw–Curtis) or non-nested (Gauss–Legendre) abscissas, verify its
sharpness numerically, and compare the performance of the resulting quasi-
optimal grids with a few alternative sparse grids construction schemes recently
proposed in literature.